/*
 * @lc app=leetcode.cn id=437 lang=typescript
 *
 * [437] 路径总和 III
 */

// @lc code=start
/**
 * Definition for a binary tree node.
 * class TreeNode {
 *     val: number
 *     left: TreeNode | null
 *     right: TreeNode | null
 *     constructor(val?: number, left?: TreeNode | null, right?: TreeNode | null) {
 *         this.val = (val===undefined ? 0 : val)
 *         this.left = (left===undefined ? null : left)
 *         this.right = (right===undefined ? null : right)
 *     }
 * }
 */

function count(
  node: TreeNode | null,
  targetSum: number,
  sum: number,
  map: Map<number, number>
): number {
  if (node === null) return 0;
  // 累加路径上所有节点
  sum += node.val;
  // 路径和与目标的差值是否出现过，出现过的话就找到匹配
  let ans = map.get(sum - targetSum) || 0;
  // 将当前累加和存入哈希
  map.set(sum, (map.get(sum) || 0) + 1);
  // 计算左右子节点有几个匹配
  ans += count(node.left, targetSum, sum, map);
  ans += count(node.right, targetSum, sum, map);
  // 当前节点相关路径都计算过了，从哈希中删除
  map.set(sum, map.get(sum) - 1);
  return ans;
}

function pathSum(root: TreeNode | null, targetSum: number): number {
  const map: Map<number, number> = new Map();
  // 初始化，累加和等于targetSum的时候也能找到匹配数
  map.set(0, 1);
  // 递归寻找每条路径是否有匹配结果
  return count(root, targetSum, 0, map);
}
// @lc code=end
